//
// Created by 紫霄 on 2020/4/24.
//

#ifndef LEETCODE_54_H
#define LEETCODE_54_H
#include <stack>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// class Solution {
// public:
//  int kthLargest(TreeNode *root, int k) {
//    stack<TreeNode *> nodes;
//    vector<int> ans;
//    goAlongLeft(root, nodes);
//    while (!nodes.empty()) {
//      auto cur = nodes.top();
//      ans.push_back(cur->val);
//      nodes.pop();
//      cur = cur->right;
//      goAlongLeft(cur, nodes);
//    }
//    return ans[ans.size() - k];
//  }
//  void goAlongLeft(TreeNode *root, stack<TreeNode *> &nodes) {
//    while (root) {
//      nodes.push(root);
//      root = root->left;
//    }
//  }
//};
class Solution {
public:
  int kthLargest(TreeNode *root, int k) {
    stack<TreeNode *> nodes;
    vector<int> ans;
    int cnt = 0;
    goAlongLeft(root, nodes);
    while (!nodes.empty()) {
      auto cur = nodes.top();
      if (++cnt == k) {
        return cur->val;
      }
      nodes.pop();
      cur = cur->left;
      goAlongLeft(cur, nodes);
    }
    return -1;
  }
  void goAlongLeft(TreeNode *root, stack<TreeNode *> &nodes) {
    while (root) {
      nodes.push(root);
      root = root->right;
    }
  }
};
#endif // LEETCODE_54_H
